package com.zhanghp.class032;

import java.util.HashSet;

/**
 * 位图的实现
 * <br/>
 * Bitset(int size)
 * <br/>
 * void add(int num)
 * <br/>
 * void remove(int num)
 * <br/>
 * void reverse(int num)
 * <br/>
 * boolean contains(int num)
 * <br/>
 *
 * @author zhanghp
 * @since 2024/4/9 9:46
 */
public class Code01_Bitset {

    public static void main(String[] args) {
        int test_time = 1000;
        int n = 100;
        System.out.println("测试开始");
        HashSet<Integer> set = new HashSet<>();
        Bitset bitset = new Bitset(100);
        System.out.println("调用阶段开始");
        for (int i = 0; i < test_time; i++) {
            double random = Math.random();
            int num = (int) (random * n);
            if (random < 0.33) {
                bitset.add(num);
                set.add(num);
            } else if (random < 0.66) {
                bitset.remove(num);
                set.remove(num);
            } else {
                bitset.reverse(num);
                if (set.contains(num)) {
                    set.remove(num);
                } else {
                    set.add(num);
                }
            }
        }
        System.out.println("调用阶段结束");
        System.out.println("验证阶段开始");
        for (int i = 0; i < n; i++) {
            if (set.contains(i) != bitset.contains(i)) {
                System.out.println("出错了");
            }
        }
        System.out.println("验证阶段结束");
        System.out.println("测试结束");
    }

    static class Bitset {
        public int[] bitset;

        public Bitset(int n) {
            // a/b如果结果想向上取整，可以写成 : (a+b-1)/b
            // 前提是a和b都是非负数
            bitset = new int[(n + 31) / 32];
        }

        public void add(int num) {
            bitset[num / 32] |= 1 << (num % 32);
        }

        public void remove(int num) {
            // 反码
            bitset[num / 32] &= ~(1 << (num % 32));
        }

        /**
         * 反转指定数的状态,若为1，则改为0，反之同理
         * <p>
         * 1:存在
         * <br/>
         * 0:不存在
         *
         * @param num
         */
        public void reverse(int num) {
            bitset[num / 32] ^= 1 << (num % 32);
        }

        public boolean contains(int num) {
            // return (bitset[num / 32] & 1 << (num % 32)) == 1;
            return ((bitset[num / 32] >> (num % 32)) & 1) == 1;
        }
    }


}
